//
//  Problem64.swift
//  TestProject
//
//  Created by 武侠 on 2021/2/25.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 64. 最小路径和
 给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

 说明：每次只能向下或者向右移动一步。

 示例 1：


 输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
 输出：7
 解释：因为路径 1→3→1→1→1 的总和最小。
 示例 2：

 输入：grid = [[1,2,3],[4,5,6]]
 输出：12
  

 提示：

 m == grid.length
 n == grid[i].length
 1 <= m, n <= 200
 0 <= grid[i][j] <= 100
 */
@objcMembers class Problem64: NSObject {
    func solution() {
        print(minPathSum([[1,3,1]]))
        print(minPathSum([[1,3,1],[1,5,1]]))
        print(minPathSum([[1,3,1],[1,5,1],[4,2,1]]))
        
        print(minPathSum([[1,2,3],[4,5,6]]))
    }
    
    /*
     动态规划
     1: 创建二维数组：dp[m][n]
     2: dp[i][j]: [i][j]到[m][n]的最短距离
        dp[i][j] = grid[i][j] + min(dp[i+1][j], dp[i][j])
     */
    func minPathSum(_ grid: [[Int]]) -> Int {
        if grid.count == 0 {
            return 0
        } else if grid.count == 1 {
            return grid[0].reduce(0) { (first, second) -> Int in
                return first + second
            }
        }
        
        var dp = Array(repeating: Array(repeating: -1, count: grid[0].count), count: grid.count)
        dp[grid.count-1][grid[0].count-1] = grid.last?.last ?? 0
        
        return getMinPathSumDP(grid, &dp, 0, 0)
    }
    
    func getMinPathSumDP(_ grid: [[Int]], _ dp: inout [[Int]], _ i: Int, _ j: Int) -> Int {
        if i >= grid.count ||  j >= grid[0].count {
            return Int.max
        }
        
        if dp[i][j] != -1 {
            return dp[i][j]
        }
        
        dp[i][j] = grid[i][j] + min(getMinPathSumDP(grid, &dp, i+1, j), getMinPathSumDP(grid, &dp, i, j+1))
        return dp[i][j]
    }
}
